package com.epam;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;



public class Graph {

	private Integer[][] graph = new Integer[][]{
			{0, 1, 8, null, 7}, 
			{1, 0, 9, null, null}, 
			{8, 9, 0, 4, null},
			{null, null, 4, 0, 8},
			{7, null, null, 8, 0}};

	public static void main(String[] args){

		Graph graphApp = new Graph();
		System.out.println(Arrays.deepToString(graphApp.graph));
		graphApp.printArray(graphApp.graph);

		graphApp.findPath(graphApp.graph);

	}

	void printArray(Integer[][] array){
		for(Integer[] deepArray:array){
			System.out.println(Arrays.deepToString(deepArray));
		}
	}

	void findPath(Integer[][] inputArray){

		Map<Integer, Integer> izKakihMozhnoDvigatsy = new HashMap<Integer, Integer>(); 
		List<Integer> vKakyjuNadoPriti = new ArrayList<Integer>();
		List<Integer> prohibitedVertices = new ArrayList<Integer>();

		for(int row = 0; row < inputArray.length; row++){
			izKakihMozhnoDvigatsy.clear();
			vKakyjuNadoPriti.clear();
			prohibitedVertices.add(row);
			Integer value;
			
			for(int j = 0; j < inputArray[row].length; j++){
				value = inputArray[row][j];
				if(value == null){
					vKakyjuNadoPriti.add(j);
				}else if(value != 0){
					izKakihMozhnoDvigatsy.put(j, value);
				}
			}

			for(Integer col:vKakyjuNadoPriti){
				System.out.println(col);
				for(Integer key:izKakihMozhnoDvigatsy.keySet()){
					
					System.out.println(findPath(inputArray, key, inputArray[row][key],
							prohibitedVertices, row, col));	
				}			
			}
			System.out.println(prohibitedVertices);
			prohibitedVertices.clear();
		}

	}

	private int findPath(Integer[][] inputArray, int vertex, int dist, List<Integer> prohibitedVertices, int row, int stolbikKydanadoPridti) {

		Integer curValue;

		for(int j = 0; j < inputArray[vertex].length; j++){
			curValue = inputArray[vertex][j];
			if(curValue != null && curValue != 0 && j != row){
				if (j == stolbikKydanadoPridti) {
					return dist + curValue;
				}
				else{
					prohibitedVertices.add(vertex);
					
				}
			}
		}
		return 0;
	}


}




